package primary.code05_Tree;

/**
 * leetcode https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/
 *
 * @author Yudi Wang
 * @date 2021/7/12 17:34
 * <p>
 * 平衡二叉树也叫AVL树，它或者是一颗空树，具有以下性质的二叉排序树
 * 它的左子树和左子树的高度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。
 */
public class Code07_BalanceBinaryTree {


    private static ReturnData judgeBBT(Node head) {
        if (head == null) return new ReturnData(true, 0);
        ReturnData left = judgeBBT(head.left);
        ReturnData right = judgeBBT(head.right);
        if (left.isBalanceTree && right.isBalanceTree
                && Math.abs(left.height - right.height) <= 1) {
            return new ReturnData(true, Math.max(left.height, right.height) + 1);
        } else {
            return new ReturnData(false, -1);
        }
    }

    private static ReturnData judgeBBTTest(Node head) {
        if (head == null) return new ReturnData(true, 0);
        ReturnData lrd = judgeBBTTest(head.left);
        ReturnData rrd = judgeBBTTest(head.right);
        boolean isBalanceTree = lrd.isBalanceTree && rrd.isBalanceTree && Math.abs(lrd.height - rrd.height) <= 1;
        return new ReturnData(isBalanceTree, Math.max(lrd.height, rrd.height) + 1);

    }

    static class ReturnData {
        //是否为平衡二叉树
        private boolean isBalanceTree;
        //树最大高度
        private int height;

        public ReturnData(boolean isBalanceTree, int height) {
            this.isBalanceTree = isBalanceTree;
            this.height = height;
        }
    }

    public static void main(String[] args) {
        Node head = new Node(4);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.right.left = new Node(7);
        head.right.right = new Node(9);
        head.right.right.right = new Node(10);
//        head.right.right.right.right = new Node(11);//注释则为平衡树
        boolean res1 = judgeBBT(head).isBalanceTree;
        boolean res2 = judgeBBTTest(head).isBalanceTree;
        System.out.println(res1);
        System.out.println(res2);
    }

}
